package com.learn.algorlthm;

/**
 * @classname:
 * @Description:礼物的最大价值
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-08-10 16:23
 * 题目描述：
 * 在一个 m*n 的棋盘的每一个格都放有一个礼物，每个礼物都有一定价值（大于 0）。从左上角开始拿礼物，每次向右或向下
 * 移动一格，直到右下角结束。给定一个棋盘，求拿到礼物的最大价值。例如，对于如下棋盘
 *
 * 1    10   3    8
 * 12   2    9    6
 * 5    7    4    11
 * 3    7    16   5
 */
public class Learn47 {

    public static int getMost(int[][] values) {
        if (values == null || values.length ==0 || values[0].length ==0)
            return 0;

        int n = values[0].length;
        int[] ret = new int[n];

        for (int[] row : values) {
            ret[0] += row[0];
            for (int i = 1; i < n; i++) {
                ret[i] = Math.max(ret[i], ret[i-1]) + row[i];
            }
        }

        return ret[n - 1];
    }
}
